package LinkList;

public class LinkList implements Define{
    //定义一个内部类(没有什么实际作用!!!,就是为了方便能在一个java文件中实现只有一个类的作用)
    public ListNode head;   //定义一个头结点

    @Override
    public void display() {
        ListNode cur=head;
        while(cur!=null) {
            System.out.print(cur.data+" ");
            cur=cur.next;
        }
        System.out.println();
    }

    @Override
    public void display(ListNode newhead) {
        ListNode cur=newhead;
        while(cur!=null) {
            System.out.print(cur.data+" ");
            cur=cur.next;
        }
        System.out.println();
    }

    //从后往前递归打印链表
    public void print(ListNode node) {
        if(node==null) {              //链表为空时不打印
            return;
        }
        if(node.next==null) {                    //如果只有一个结点那么就打印完这个结点后直接返回
            System.out.print(node.data+" ");
            return;
        }
        print(node.next);
        System.out.print(node.data+" ");
    }
    @Override
    public void addFirst(int data) {
        ListNode newListNode=new ListNode(data);
        newListNode.next=head;
        head=newListNode;
    }

    @Override
    public void addLast(int data) {
        ListNode newListNode=new ListNode(data);
        if(head==null) {
            head=newListNode;
        }else {
            ListNode cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = newListNode;//此时的cur就是尾巴
        }
    }

    @Override
    public boolean contains(int key) {
        ListNode cur=head;
        while(cur!=null) {
            if(cur.data==key) {
                return true;
            }
            cur=cur.next;
        }
        return false;
    }

    @Override
    public int size() {
        int count=0;
        ListNode cur=head;
        while(cur!=null) {
            cur=cur.next;
            count++;
        }
        return count;
    }

    @Override
    public ListNode get(int data) {
        ListNode cur=head;
        while(cur!=null) {
            if(cur.data==data) {
                return cur;
            }
            cur=cur.next;
        }
        return null;
    }
    @Override
    public ListNode getIndex(int index) {
        checkIndex(index);
        int count=0;
        ListNode cur=head;
        while(cur!=null) {
            if(count==index) {
                return cur;
            }
            count++;
            cur=cur.next;
        }
        return null;
    }

    @Override
    public void addIndex(int index, int data) {
        this.checkIndex(index);
        int count=0;
        ListNode newListNode=new ListNode(data);
        ListNode cur=head;
        if(index==0) {   //相当于头插
            newListNode.next = head;
            head = newListNode;
        }else {
            while ((count++) != index - 1) {    //这样相当于找到了要增加数据位置的前一个结点
                cur = cur.next;
            }
            newListNode.next = cur.next;
            cur.next = newListNode;
        }
    }
    private void checkIndex(int index) {
        if(index<0||index>this.size()) {
            throw new CheckIndexOutOfException("位置输入有误!");
        }
    }
    @Override
    public void remove(int key) {
        ListNode cur=head;
//        if(head==null) {    //没有结点时直接返回（不加这句话的原因是:当head为null的时候，cur也为null这样就不会执行下面的代码，如果需要执行head.data
//        那么就要判断是否为null，否则就会出现空指针异常）
//            return;
//        }
        while(cur!=null) {
            if(head.data==key) {
                head=head.next;
                break;
            }else {
                if (cur.next.data == key) {     //如果cur的下一个结点的data等于key，那么就相当于找到了需要删除位置的前一个结点
                    cur.next = cur.next.next;
                    break;
                }
            }
            cur=cur.next;
        }
    }

    @Override
    public void removeAll(int key) {
        ListNode cur=head;
        ListNode prevListNode=null;
        while(cur!=null) {
            if(head.data==key) {
                head=head.next;
            }else {
                if (cur.data == key) {
                    prevListNode.next = cur.next;     //如果相邻两个都是key，那么要让prevListNode不动，不然prevListNode就会指向原来删去的cur位置
                    cur = prevListNode.next;
                    continue;
                }
            }
            prevListNode=cur;
            cur=cur.next;
        }
    }

    @Override
    public void clear() {
        head=null;       //系统会自动回收
    }
}
